package MAIN;
//动态规划算法课程练习
public class LeetCodePractice {
    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        //1.创建一个dp表
        //2.初始化  3.填表  4.返回值
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) dp[i] = 1;
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    //打家劫舍I
    public int rob1(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        g[0] = 0;
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }
    //打家劫舍II
    public int rob2(int[] nums) {
        int len = nums.length;
        //首先按照偷最后一个屋子和不偷一个屋子进行分类，返回的是二者之间的最大值
        return Math.max(nums[0] + rob1(nums,2,len-2),
                rob1(nums,1,len-1));
    }
    //然后传递过来的区间就按照打家劫舍I的算法来处理即可  （可以在这个区间随便偷，只要不是相邻的即可）
    private int rob1(int[] nums, int left, int right) {
        if (left > right) return 0;
        //1.创建dp表，  2.初始化  3.填表  4.返回
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];//代表的是第一个要偷
        g[left] = 0;//代表的是第一个不偷
        for (int i = left; i <= right; i++) {
            f[i] = g[i - 1] + nums[i];
            //如果i下标的位置不偷，此时i-1下标的位置有两种选择：偷 / 不偷（然后也是取最大值）
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }
        return Math.max(f[right], g[right]);
    }

    //按摩师
    public int massage(int[] nums) {
        //1.创建dp表（创建两个dp表）
        //2.初始化
        //3.填表
        //4.返回值
        int len = nums.length;
        int[] f = new int[len];
        int[] g = new int[len];
        if (len == 0) return 0;
        f[0] = nums[0];
        for (int i = 0; i < len; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[len-1], g[len-1]);
    }

    //解码方法
    //1.状态表示: dp[i]表示以位置为结尾时，解码的方法的总数
    //2.状态转移方程（根据最近的一步来划分你问题）：2种解码方式，都有成功或者失败，只要最后一个
    //字符解码失败，此时总的方案数就是0，
    public int numDecodings(String s) {
        //1.创建dp表  2.初始化   3.填表    4.返回值
        int n = s.length();
        char[] chs = s.toCharArray();
        int[] dp = new int[n];
        //初始化第一个位置
        if (chs[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];//如果只有一个字符，此时就返回dp0即可

        //初始化第二个位置
        if (chs[1] != '0' && chs[0] !='0') dp[1] += 1;
        int t = (chs[0] - '0') * 10 + chs[1] - '0';
        if (t >=10 && t <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            //处理第一种情况
            if (chs[i] != '0') dp[i] += dp[i-1];
            //处理第二种情况
            int t2 = (chs[i-1]-'0')*10 + chs[i] -'0';
            if (t2 >= 10 && t2 <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }


    //最小花费爬楼梯:给定的数组不是最后一个就是楼顶，
    // 而是数组啊最后的后一个数(数组之的数)是楼顶
    //算法原理2（以i位置为起点）
    //算法原理1（以i位置为终点）
    public int minCostClimbingStairs2(int[] cost) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = cost.length;
        int[] dp = new int[n];
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for (int i = n-3; i >=0; i--) {
            dp[i] = Math.min(dp[i+1],dp[i+2]) + cost[i];
        }
        return Math.min(dp[0], dp[1]);
    }
    public static int minCostClimbingStairs1(int[] cost) {
        //1.状态表示 2.状态转移方程 3.初始化  4.填表顺序  5.确定返回值
        //确定初始化的值
        int n = cost.length;
        int[] dp = new int[n+1];
        for (int i = 2 ; i <= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int[] arr = {10,15,20};
        System.out.println(minCostClimbingStairs1(arr));;
    }
    //三步问题
    public int waysToStep(int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        //处理边界条件
        //1e9可能是一个double的类型，需要强转
        int MOD = (int)1e9 + 7;
        if (n == 1 || n == 2) return n;
        if (n == 3) return 4;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }
        return dp[n];
    }
    public int tribonacci(int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //返回值
        //处理一下边界情况
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        //要返回第n个数据就要初始化n+1
        int[] dp = new int[n+1];
        dp[0] = 0;dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
    public int tribonacci2(int n) {
        //空间优化
        int a = 0,b = 1,c = 1,d = 0;
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

}
